package org.example.Monotone_stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class The_next_bigger_element_I {
    public static void main(String[] args) {
        //下一个更大元素 I

        //nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
        //给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
        //对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
        //返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        int[] ints = nextGreaterElement(nums1, nums2);
        System.out.println(Arrays.toString(ints));
    }

    //暴力解3ms
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]){
                    j++;
                    while(j < nums2.length){
                        if (nums2[j] > nums1[i]){
                            res[i] = nums2[j];
                            break;
                        }
                        j++;
                    }
                    if (res[i] == 0){
                        res[i] = -1;
                    }
                    break;
                }
            }
        }
        return res;
    }
}
